package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/9/20 11:34 AM
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 */
public class _123_买卖股票的最佳时机_III_02 {

    public int maxProfit(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }



        int len = prices.length;

        int[] leftToRight = new int[len];
        int[] rightToLeft = new int[len];

        int leftMin = prices[0];
        for (int i = 1; i < prices.length; i++) {



            leftToRight[i] = Math.max(leftToRight[i - 1], prices[i] - leftMin);
            if (prices[i] < leftMin) {

                leftMin = prices[i];
            }
        }


        int rightMax = prices[len - 1];
        for (int i = len - 2; i >= 0; i--) {


            rightToLeft[i] = Math.max(rightToLeft[i + 1], rightMax - prices[i]);

            if (rightMax < prices[i]) {

                rightMax = prices[i];
            }
        }

        int max = rightToLeft[0];
        for (int i = 0; i < len - 1; i++) {


            max = Math.max(max,leftToRight[i] + rightToLeft[i+1]);
        }

        return max;
    }


}
